package com.sise.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 *      77. 组合
 *
 *      给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 *      你可以按 任何顺序 返回答案。
 *
 *      输入：n = 4, k = 2
 *      输出：
 *      [
 *        [2,4],
 *        [3,4],
 *        [2,3],
 *        [1,2],
 *        [1,3],
 *        [1,4],
 *      ]
 */
public class _77_combine {
    public List<List<Integer>> combine(int n, int k) {

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        dfs(n, k, 1, result, path);
        return result;
    }

    private void dfs(int n, int k, int begin, List<List<Integer>> result, List<Integer> path) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }

        // 事实上，如果 n = 7, k = 4，从 5 开始搜索就已经没有意义了，故此在 for 循环中可以再次进行剪枝
        // 搜索起点的上界 + 接下来要选择的元素个数 - 1 = n
        // 搜索起点的上界 = n - (k - path.size()) + 1
        for (int cur = begin; cur <= n - (k - path.size()) + 1; cur++) {
            path.add(cur);
            dfs(n, k, cur + 1, result, path);
            path.remove(path.size() - 1);
        }
    }
}
